/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 // 迭代 前序 翻转
 // 中 左 右
 // 右 左 中
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    st := list.New()
    st.PushBack(root)

    for st.Len() > 0 {
        e := st.Remove(st.Back())
        if e == nil {
            node := st.Remove(st.Back()).(*TreeNode)
            node.Left, node.Right = node.Right, node.Left
            continue
        }
        node := e.(*TreeNode)
        // 右
        if node.Right != nil {
            st.PushBack(node.Right)
        }
        // 左
        if node.Left != nil {
            st.PushBack(node.Left)
        }
        // 中
        st.PushBack(node)
        st.PushBack(nil)
    }
    return root
}